# -*- encoding: utf-8 -*-


def binary_search(sorted_list, item):
    """普通的二分查找"""
    left, right = 0, len(sorted_list) - 1
    while right >= left:
        mid = left + (right - left) // 2
        current_item = sorted_list[mid]
        if current_item == item:
            return current_item
        if current_item > item:
            right = mid - 1
        else:
            left = mid + 1
    return None


def binary_search_by_recursion(sorted_list, item):
    """递归方法的二分查找"""
    left, right = 0, len(sorted_list)
    if right <= left:
        return None
    mid = (right - left) // 2
    current_item = sorted_list[mid]
    if current_item == item:
        return item
    if current_item > item:
        sorted_list = sorted_list[left: mid]
    else:
        sorted_list = sorted_list[mid + 1: right]

    return binary_search_by_recursion(sorted_list, item)


def binary_search_last_leq(sorted_list, item):
    """sorted_list中查找最后一个小于等于item的数"""
    left, right = 0, len(sorted_list) - 1
    while right >= left:
        mid = left + (right - left) // 2
        current_item = sorted_list[mid]
        if current_item == item:
            return current_item
        if current_item > item:
            right = mid - 1
        else:
            if sorted_list[mid + 1] > item:
                return sorted_list[mid + 1]
            else:
                left = mid + 1
    return None


if __name__ == '__main__':
    print(binary_search([8, 11, 19, 23, 27, 33, 45, 55, 67, 98], 19))
    print(binary_search_by_recursion([8, 11, 19, 23, 27, 33, 45, 55, 67, 98], 19))
    print(binary_search_last_leq([8, 11, 19, 23, 27, 33, 45, 55, 67, 98], 10))
